package 分类.一维动规;

public class 矩阵的最小路径和 {
    public static int minPathSum (int[][] matrix) {
        // write code here
        int res=0;
        int m=matrix.length;
        int n=matrix[0].length;
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if(i==0&&j!=0){
                    matrix[i][j]+=matrix[i][j-1];
                }else if(i!=0&&j==0){
                    matrix[i][j]+=matrix[i-1][j];
                }else if(i!=0&&j!=0){
                    matrix[i][j]+=Math.min(matrix[i-1][j],matrix[i][j-1]);
                }
            }
        }

        return matrix[m-1][n-1];
    }

    public static void main(String[] args) {
        int[][] nums={{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
        System.out.println(minPathSum(nums));
    }
}
